package two.chapter_4.c4_4;

import two.chapter_1.c1_3.LinkStack;
import two.chapter_1.c1_3.Stack;
import two.chapter_2.c2_4.IndexMinPQ;

/**
 * 最短路径
 */
public class DijkstraSP {
    private DirectedEdge[] edgeTo;
    private double[] distTo;
    private IndexMinPQ<Double> pq;
    public DijkstraSP(EdgeWeightedDigraph g, int s){

        edgeTo=new DirectedEdge[g.v()];
        distTo=new double[g.v()];
        pq=new IndexMinPQ<>(g.v());
        for (int i=0;i<g.v();i++){
            distTo[i]=Double.POSITIVE_INFINITY;
        }
        distTo[s]=0.0;
        pq.insert(s,0.0);
        while (!pq.isEmpty()){
            relax(g,pq.delMin());
        }
    }
    private void relax(EdgeWeightedDigraph g,int v){
        for (DirectedEdge e:g.adj(v)){
            int w=e.to();
            if (distTo[w]>distTo[v]+e.weight()){
                distTo[w]=distTo[v]+e.weight();
                edgeTo[w]=e;
                if (pq.contains(w)){
                    pq.changeKey(w,distTo[w]);
                }else {
                    pq.insert(w,distTo[w]);
                }
            }
        }
    }



    private void relax(DirectedEdge e){
        int v=e.from();
        int w=e.to();
        if (distTo[w]>distTo[v]+e.weight()){
            distTo[w]=distTo[v]+e.weight();
            edgeTo[w]=e;
        }

    }
    /**
     * 从顶点s到v的距离，如果不存在则路径为无穷大
     * @param v
     * @return
     */
    public double distTo(int v){
        return distTo[v];
    }

    /**
     * 是否存在从s到v的路径
     * @param v
     * @return
     */
    public boolean hasPathTo(int v){
        return distTo[v]<Double.POSITIVE_INFINITY;
    }

    public Iterable<DirectedEdge> pathTo(int v){
        if (hasPathTo(v)){
            Stack<DirectedEdge> path=new LinkStack<>();
            for (DirectedEdge e=edgeTo[v];e!=null;e=edgeTo[e.from()]){
                path.push(e);
            }
            return path;
        }
        return null;
    }

}
